# 每一位要过河的人的过河用时，忽略0号位进行对齐
a = [0, 1, 2, 5, 10]
# 人数
n = 4
# 最短时间
s = 0
# 如果人数大于3，则用贪心法缩小问题规模，直到人数小于等于3人
while n > 3:
    # 过河策略1:
    # step1: 当前未过河的人里，最快和最慢过河，到达对岸的人里，最快的回来，用时：a[n] + a[1]
    # step2: 当前未过河的人里，最快和最慢过河，到达对岸的人里，最快的回来，用时：a[n-1] + a[1]
    # 不断重复step1和step2的操作每次可以送2个人到对岸
    # 送两个人过河总耗时：a[n] + a[1] + a[n-1] + a[1] = a[1] * 2 + a[n-1] + a[n]
    # 过河策略2:
    # step1: 当前未过河的人里，最快和次快过河，到达对岸的人里，最快的回来，用时:a[2] + a[1]
    # step2: 当前未过河的人里，最慢和次慢过河，到达对岸的人里，最快的回来，用时:a[n] + a[2]
    # 不断重复step1和step2的操作每次可以送2个人到对岸
    # 送两个人过河总耗时：a[2] + a[1] + a[n] + a[2] = a[1] + a[2] * 2 + a[n]
    # 上述两个策略有时候策略1更好有时候策略2更好，所以取最小值
    s += min(a[1] * 2 + a[n - 1] + a[n], a[1] + a[2] * 2 + a[n])
    # 每次送两个人过河
    n -= 2
# 如果剩下1人，则直接把时间加上
if n == 1:
    s += a[1]
# 如果剩下2人，则取a[2]因为两人过河速度由慢的人决定，而a列表是从小到达排列的
elif n == 2:
    s += a[2]
# 如果剩下3人，则三人过河的耗时恰好是三个人过河时间的总和
else:
    s += a[1] + a[2] + a[3]

print("s = ", s)
